package org.nowcoder.leetcode.sort;

import java.util.*;

/**
 * Title  : 23. Merge k Sorted Lists
 * Source : https://leetcode.cn/problems/merge-k-sorted-lists
 * Author : XrazYang
 * Date   : 2023-09-19
 */

public class LeetCode_23 {
    class ListNode {
        public int val;
        public ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        //朴素解法：
        List<Integer> vals = new ArrayList<>();
        //排序
        for (ListNode list : lists) {
            ListNode node = list;
            while (node != null) {
                vals.add(node.val);
                node = node.next;
            }
        }
        //构建链表
        Collections.sort(vals);
        ListNode root = new ListNode(), p = root;
        for (Integer val : vals) {
            ListNode node = new ListNode(val);
            p.next = node;
            p = node;
        }
        return root.next;
    }
}
